package com.cat.dataStructure02;

import java.util.Arrays;

/**
 * @author 曲大人的喵
 * @description https://leetcode.cn/problems/largest-component-size-by-common-factor/
 * @create 2025/10/10 10:53
 * @since JDK17
 */

public class Solution10 {
    static int N = ((int) (1e5 + 10)), n;
    static int[] factor = new int[N];
    int[] size, f;
    int find(int x) {
        if (x != f[x]) {
            f[x] = find(f[x]);
        }
        return f[x];
    }

    void union(int x, int y) {
        int fx = find(x), fy = find(y);
        if (fx != fy) {
            f[fx] = fy;
            size[fy] += size[fx];
        }
    }

    public int largestComponentSize(int[] nums) {
        n = nums.length;
        f = new int[n];
        size = new int[n];
        int ans = 0;
        for (int i = 0; i < n; i++) {
            size[i] = 1;
            f[i] = i;
        }
        Arrays.fill(factor, 0, N, -1);
        for (int i = 0; i < n; i++) {
            int num = nums[i];
            for (int j = 2; j * j <= num; j++) {
                if (num % j == 0) {
                    if (factor[j] == -1) {
                        factor[j] = i;    //
                    } else {
                        union(factor[j], i);
                    }
                    while (num % j == 0) {
                        num /= j;
                    }
                }
            }
            if (num > 1) {
                if (factor[num] == -1) {
                    factor[num] = i;    //
                } else {
                    union(factor[num], i);
                }
            }
        }
        for (int i = 0; i < n; i++) {
            ans = Math.max(ans, size[i]);
        }
        return ans;
    }
}
